home *** CD-ROM | disk | FTP | other *** search
/ System Booster / System Booster.iso / Archives / GNU / groff_src.lha / groff-1.10src / troff / symbol.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-22  |  3.9 KB  |  151 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  20.  
  21.  
  22. #include "troff.h"
  23. #include "symbol.h"
  24.  
  25. const char **symbol::table = 0;
  26. int symbol::table_used = 0;
  27. int symbol::table_size = 0;
  28. char *symbol::block = 0;
  29. int symbol::block_size = 0;
  30.  
  31. const symbol NULL_SYMBOL;
  32.  
  33. #ifdef BLOCK_SIZE
  34. #undef BLOCK_SIZE
  35. #endif
  36.  
  37. const int BLOCK_SIZE = 1024;
  38. // the table will increase in size as necessary
  39. // the size will be chosen from the following array
  40. // add some more if you want
  41. // I think it unlikely that we'll need more than a million symbols
  42. static const unsigned int table_sizes[] = { 
  43. 101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009, 80021, 160001, 500009, 1000003, 0 
  44. };
  45. const double FULL_MAX = 0.3;    // don't let the table get more than this full
  46.  
  47. static unsigned int hash_string(const char *p)
  48. {
  49.   // compute a hash code; this assumes 32-bit unsigned ints
  50.   // see p436 of  Compilers by Aho, Sethi & Ullman
  51.   // give special treatment to two-character names
  52.   unsigned int hc = 0, g;
  53.   if (*p != 0) {
  54.     hc = *p++;
  55.     if (*p != 0) {
  56.       hc <<= 7;
  57.       hc += *p++;
  58.       for (; *p != 0; p++) {
  59.     hc <<= 4;
  60.     hc += *p;
  61.     if ((g = (hc & 0xf0000000)) == 0) {
  62.       hc ^= g >> 24;
  63.       hc ^= g;
  64.     }
  65.       }
  66.     }
  67.   }
  68.   return hc;
  69. }
  70.  
  71. // Tell compiler that a variable is intentionally unused.
  72. inline void unused(void *) { }
  73.  
  74. symbol::symbol(const char *p, int how)
  75. {
  76.   if (p == 0 || *p == 0) {
  77.     s = 0;
  78.     return;
  79.   }
  80.   if (table == 0) {
  81.     table_size = table_sizes[0];
  82.     table = (const char **)new char*[table_size];
  83.     for (int i = 0; i < table_size; i++)
  84.       table[i] = 0;
  85.     table_used = 0;
  86.   }
  87.   unsigned int hc = hash_string(p);
  88.   const char **pp;
  89.   for (pp = table + hc % table_size; 
  90.        *pp != 0; 
  91.        (pp == table ? pp = table + table_size - 1 : --pp))
  92.     if (strcmp(p, *pp) == 0) {
  93.       s = *pp;
  94.       return;
  95.     }
  96.   if (how == MUST_ALREADY_EXIST) {
  97.     s = 0;
  98.     return;
  99.   }
  100.   if (table_used  >= table_size - 1 || table_used >= table_size*FULL_MAX) {
  101.     const char **old_table = table;
  102.     unsigned int old_table_size = table_size;
  103.     int i;
  104.     for (i = 1; table_sizes[i] <= old_table_size; i++)
  105.       if (table_sizes[i] == 0)
  106.     fatal("too many symbols");
  107.     table_size = table_sizes[i];
  108.     table_used = 0;
  109.     table = (const char **)new char*[table_size];
  110.     for (i = 0; i < table_size; i++)
  111.       table[i] = 0;
  112.     for (pp = old_table + old_table_size - 1; 
  113.      pp >= old_table;
  114.      --pp) {
  115.        symbol temp(*pp, 1); /* insert it into the new table */
  116.        unused(&temp);
  117.      }
  118.     a_delete old_table;
  119.     for (pp = table + hc % table_size;
  120.      *pp != 0; 
  121.      (pp == table ? pp = table + table_size - 1 : --pp))
  122.       ;
  123.   }
  124.   ++table_used;
  125.   if (how == DONT_STORE) {
  126.     s = *pp = p;
  127.   }
  128.   else {
  129.     int len = strlen(p)+1;
  130.     if (block == 0 || block_size < len) {
  131.       block_size = len > BLOCK_SIZE ? len : BLOCK_SIZE;
  132.       block = new char [block_size];
  133.     }
  134.     (void)strcpy(block, p);
  135.     s = *pp = block;
  136.     block += len;
  137.     block_size -= len;
  138.   }
  139. }
  140.  
  141. symbol concat(symbol s1, symbol s2)
  142. {
  143.   char *buf = new char [strlen(s1.contents()) + strlen(s2.contents()) + 1];
  144.   strcpy(buf, s1.contents());
  145.   strcat(buf, s2.contents());
  146.   symbol res(buf);
  147.   a_delete buf;
  148.   return res;
  149. }
  150.  
  151.